matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
#整体使用循环迭代求解，每一行使用使用二分查找求解
#时间复杂度：o(nlogn)
def searchMatrix(matrix,target):
    rowLen=len(matrix)
    colLen=len(matrix[0])

    for i in range(rowLen):
        print("i:",i)
        left,right=0,colLen-1
        print(matrix[i][left],matrix[i][right])
        if matrix[i][left]>target or matrix[i][right]<target:
            #本行没有，进行下一行的遍历
            continue
        while left<=right:
            mid=(left+right)>>1
            if i==1:
                print(mid)
            if matrix[i][mid]==target:
                return True
            if matrix[i][mid]<target:
                left=mid+1
            if matrix[i][mid]>target:
                right=mid-1
    return False
#
def searchMatrix1(matrix,target):
    #行数和列数
    rowLen=len(matrix)
    colLen=len(matrix[0])
    #初始搜索位置
    curIndexR=0
    curIndexC=colLen-1
    while curIndexR>=0 and curIndexR<rowLen and curIndexC>=0 and curIndexC<colLen:
        if matrix[curIndexR][curIndexC]==target:
            return True
        if matrix[curIndexR][curIndexC]>target:
            curIndexC-=1
        if matrix[curIndexR][curIndexC]<target:
            curIndexR+=1
    return False
print(searchMatrix1(matrix,5))
